'''
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。



 

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
'''
class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        arr = []
        dic = {'2':['a','b','c'],
               '3':['d','e','f'],
               '4':['g','h','i'],
               '5':['j','k','l'],
               '6':['m','n','o'],
               '7':['p','q','r','s'],
               '8':['t','u','v'],
               '9':['w','x','y','z']}

        def get_list(arr,digit):
            if arr == []:
                arr = dic[digit]
            else:
                arr = arr*len(dic[digit])
                arr.sort()
                tmp = dic[digit]*int(len(arr)/len(dic[digit]))
                for i in range(len(arr)):
                    arr[i] = arr[i]+tmp[i]
            return arr

        for d in digits:
            arr = get_list(arr,d)
        return arr

digits = "22"
Solution().letterCombinations(digits)